package com.zlei.code.binaryTree.traversal;

/**
 * @Author leizhang76
 * @Date 2021/2/19 16:43
 */


import com.zlei.code.binaryTree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


public class preTraversal {

    /**
     * 二叉树的前序遍历(先根遍历)
     * 1、访问根节点
     * 2、递归遍历左子树
     * 3、递归遍历右子树
     */
    public void preTravel(TreeNode treeNode){
        if (treeNode!=null){
            System.out.println(treeNode.val);
            preTravel(treeNode.left);
            preTravel(treeNode.right);
        }
    }

    /**
     * 二叉树的非递归的遍历实现思想:
     *
     * 借助栈，对于根节点，先将当前节点压入栈中，然后遍历的时候弹出栈中的一个元素，输出，
     * 当该节点的右节点不为空时，将节点压入栈，当左节点不为空时，
     * 将左节点压入栈[前序遍历是根左右但是栈的数据结构时先入后出，先访问到左节点，需要将右节点先压入栈中]。
     * 继续循环，弹出栈顶元素，输出，将右节点和左节点压入栈中...
     * @param root
     * @return
     */
    public List<Integer> preorderTravel(TreeNode root){
        List<Integer> list=new ArrayList<> (  );
        if (root==null){
            return list;
        }
        TreeNode temp=root;
        Stack<TreeNode> stack=new Stack<> ();
        //先把根节点推入栈中
        stack.push (temp);
        while (!stack.isEmpty ()){
            TreeNode res = stack.pop ( );
            list.add (res.val);
            if (res.right!=null){
                stack.push (res.right);
            }
            if (res.left!=null){
                stack.push (res.left);
            }
        }
        return list;
    }




}












